- Title
- On groups that have normal forms computable in logspace
- Creator
- Elder, Murray; Elston, Gillian; Ostheimer, Gretchen
- Relation
- Journal of Algebra Vol. 381, Issue 1, p. 260-281
- Publisher Link
- http://dx.doi.org/10.1016/j.jalgebra.2013.01.036
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2013
- Description
- We consider the class of finitely generated groups which have a normal form computable in logspace. We prove that the class of such groups is closed under passing to finite index subgroups, direct products, wreath products, and certain free products and infinite extensions, and includes the solvable Baumslag–Solitar groups, as well as non-residually finite (and hence non-linear) examples. We define a group to be logspace embeddable if it embeds in a group with normal forms computable in logspace. We prove that finitely generated nilpotent groups are logspace embeddable. It follows that all groups of polynomial growth are logspace embeddable.
- Subject
- logspace algorithm; logspace normal form; logspace embeddable; wreath product; Baumslag–Solitar group; logspace word problem
- Identifier
- http://hdl.handle.net/1959.13/938672
- Identifier
- uon:12653
- Identifier
- ISSN:0021-8693
- Rights
- © 2013. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/.
- Language
- eng
- Full Text
- Reviewed
- Hits: 2930
- Visitors: 3110
- Downloads: 271
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 256 KB | Adobe Acrobat PDF | View Details Download |